import java.util.Stack;

//字符串解码
//测试链接 https://leetcode.cn/problems/decode-string/
public class DecodeString {
    public String decodeString(String s) {
        char[] arr = s.toCharArray();
        int len = arr.length;

        Stack<StringBuilder> stack_string = new Stack<>(); //存放字符串的栈
        Stack<Integer> stack_num = new Stack<>();   //存放数字的栈
        stack_string.push(new StringBuilder());

        for(int i = 0; i < len; i++) {
            char temp = arr[i];
            if(temp >= '0' && temp <= '9') { //遇到数字提取数字
                int num = temp - '0';
                while(i+1 < len && arr[i+1] >= '0' && arr[i+1] <= '9') {
                    num = num * 10 + arr[i+1] - '0';
                    i++;
                }
                stack_num.push(num);
            }
            else if( temp >= 'a' && temp <= 'z') { //遇到字符提取字符串
                StringBuilder str = new StringBuilder();

                if(!stack_string.empty())
                    str.append(stack_string.pop());

                str.append(temp);
                while(i+1 < len && arr[i+1] >= 'a' && arr[i+1] <= 'z') {
                    str.append(arr[i+1]);
                    i++;
                }
                stack_string.add(str);
            }
            else if( temp == ']') {  //结算与']'左边最近的']'内的字符串
                int num = stack_num.pop(); //数字栈顶元素表示要循环几次
                StringBuilder str = stack_string.pop(); //栈顶字符串

                for(int j = 0; j < num; j++) {
                    stack_string.peek().append(str);
                }

            }
            //遇到'[' 把这个符号后的字符串放到栈中
            else {
                if(arr[i+1] >= 'a' && arr[i+1] <= 'z') {
                    i++;
                    StringBuilder str = new StringBuilder();
                    str.append(arr[i]);
                    while(i+1 < len && arr[i+1] >= 'a' && arr[i+1] <= 'z') {
                        str.append(arr[i+1]);
                        i++;
                    }
                    stack_string.push(str);
                }else{
                    stack_string.push(new StringBuilder());
                }
            }
        }

        return stack_string.peek().toString();
    }
}
